#pragma once

const int BASE = 10;
const int BASE_LENGTH = 1;

struct empty_list_t{};

template<size_t data, typename tail>
struct list_t
{
   static const size_t head_ = data;
   typedef tail tail_;
};

template<typename list>
struct length
{
   static const size_t result_ = 1 + length<typename list::tail_>::result_;
};

template<>
struct length<empty_list_t>
{
   static const size_t result_ = 0;
};

template<typename list, size_t value>
struct add
{
   typedef list_t<
      list::head_,
      typename add<
         typename list::tail_,
         value
      >::result_
   > result_;
};

template<int value>
struct add<empty_list_t, value>
{
   typedef list_t<
      value,
      empty_list_t
   > result_;
};

template<size_t length, typename list>
struct prefix
{
   typedef list_t<list::head_, typename prefix<length - 1, typename list::tail_>::result_> result_;
};

template<typename list>
struct prefix<0, list>
{
   typedef empty_list_t result_;
};

template<size_t length, typename list>
struct suffix
{
   typedef typename suffix<length - 1, typename list::tail_>::result_ result_;
};

template<typename list>
struct suffix<0, list>
{
   typedef list result_;
};

template<typename list>
struct reverse
{
   typedef typename add<
      typename reverse<
         typename list::tail_
      >::result_,
      list::head_
   >::result_ result_;
};

template<>
struct reverse<empty_list_t>
{
   typedef empty_list_t result_;
};

template<typename list, size_t count>
struct shift
{
   typedef list_t<
      0,
      typename shift<
         list,
         count - 1
      >::result_
   > result_;
};

template<typename list>
struct shift<list, 0>
{
   typedef list result_;
};